package com.tping.leetcode;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
 * 计算按此排列的柱子，下雨之后能接多少雨水
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
 */
public class Solution_0042 {


    /**
     * 动态规划方式
     *
     * @param height
     * @return
     */
    public int trap(int[] height){
        int len = height.length;
        int ans = 0;
        if( len < 3 ) return ans;

        /**
         * 初始化两个数组
         * 1、从左边遍历一遍，计算出柱子的最高水位
         * 2、从右边遍历一遍，计算出柱子的最高水位
         */
        int[] leftHeights = new int[len];
        int[] rightHeights = new int[len];
        leftHeights[0] = height[0];
        rightHeights[len - 1] = height[len - 1];

        for (int i = 1; i < len; i++) {
            leftHeights[i] = Math.max(leftHeights[i - 1], height[i]);
        }

        for (int i = len - 2; i >= 0; i--) {
            rightHeights[i] = Math.max(rightHeights[i + 1], height[i]);
        }

        for (int i = 0; i < len; i++) {
            ans += Math.min(leftHeights[i], rightHeights[i]) - height[i];
        }

        return ans;
    }


    public static void main(String[] args){
        int[] heights = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};

        Solution_0042 solution = new Solution_0042();
        // 正确结果：6
        System.out.println("动态规划方式解题结果：" + solution.trap(heights));
    }

}
